# 简而言之，计算的本质：是将一棵树，变换为另外一棵树。

# 研究Simple 语言中表达式的语义，需要构建一棵AST，
# 通过ruby 的类表示Simple 语法中每种不同的元素

# 表达式：
class Number < Struct.new(:value)
end

class Add < Struct.new(:left, :right)
end

class Multiply < Struct.new(:left, :right)
end

# 实例化这些类，构造AST(Abstract Syntax Tree, 即抽象语法树)
puts Add.new(
    Multiply.new(Number.new(1), Number.new(2)),
    Multiply.new(Number.new(3), Number.new(4))
)

# #<struct Add left=#<struct Multiply left=#<struct Number value=1>, 
# right=#<struct Number value=2>>, right=#<struct Multiply 
# left=#<struct Number value=3>, right=#<struct Number value=4>>>

# 为了方便查看，我们需要覆盖每个类的inspect 方法，
# 现在的irb 显示了太多不重要的细节：
class Number
    def to_s
        value.to_s
    end

    def inspect
        "<<#{self}>>"
    end
end

class Add
    def to_s
        "#{left} + #{right}"
    end

    def inspect
        "<<#{self}>>"
    end
end

class Multiply
    def to_s
        "#{left} * #{right}"
    end

    def inspect
        "<<#{self}>>"
    end
end

# 实例化以构建抽象语法树
puts Add.new(
    Multiply.new(Number.new(1), Number.new(2)),
    Multiply.new(Number.new(3), Number.new(4))
)
# 抽象语法树：1 * 2 + 3 * 4

puts Number.new(5)
# 5


# 上述对to_s 的实现未考虑运算的优先级，所以按照传统
# 优先级，它的输出有时候是不正确的，如下：
puts Multiply.new(
    Number.new(1),
    Multiply.new(
        Add.new(Number.new(2),Number.new(3)),
        Number.new(4)
    )
)
# 这棵树表示 1 * (2 + 3) * 4
# 而打印出来是这样的： 1 * 2 + 3 * 4
# 明显出错了，但是这个与关于语义的讨论没有关系
# 为了简单起见，暂时忽略这个问题，后面会给出更合适的实现

# 什么是规约(reduce)?
# 简而言之，就是一台机器，直接按照语言的语法进行操作，最后一小步小步的反复进行求值，
# 这种过程称作规约
# 如，JS 可迭代对象的reduce 方法(ruby 中的inject 方法)的计算过程，本质上就是一种规约（得到一个具体值的过程）

# 为抽象语法树定义规约方法：是实现小步操作的起点
# 抽象语法树(输入) ==> 规约树(输出)

# 什么样的表达式能规约？
# Add 与 Multiply 能规约（每个表达式表示一个操作，并能通过这
# 种操作变成一个结果），但是Number 代表一个值，不可规约其它东西，如下：


class Number
    def reducible?
        false
    end
end

class Add
    def reducible?
        true
    end
end

class Multiply
    def reducible?
        true
    end
end

puts Number.new(1).reducible?
# false

puts Add.new(Number.new(1),Number.new(2)).reducible?
# true


# 实现规约：
# 具体规则：
# 1. 如果加法左边参数能够实现，就规约左边的参数
# 2. 如果加法左边的参数不能规约，但是右边的参数可以规约，就规约右边的参数
# 3. 如果两边都不能规约，他们应该为数字，就把它们加到一起

class Add
    def reduce
        if left.reducible?
            Add.new(left.reduce, right)
        elsif right.reducible?
            Add.new(left, right.reduce)
        else
            Number.new(left.value + right.value)
        end
    end
end

# 同样的，我们仿照加法的规约，可以实现乘法的规约
class Multiply
    def reduce
        if left.reducible?
            Multiply.new(left.reduce, right)
        elsif right.reducible?
            Multiply.new(left, right.reduce)
        else
            Number.new(left.value * right.value)
        end
    end
end

# 尝试对规约进行调用
expression = Add.new(
    Multiply.new(Number.new(1), Number.new(2)),
    Multiply.new(Number.new(3), Number.new(4))
)
puts expression
# 1 * 2 + 3 * 4

puts expression.reducible?
# true

expression = expression.reduce
puts expression
# 2 + 3 * 4

puts expression.reducible?
# true

expression = expression.reduce
puts expression
# 2 + 12

puts expression.reducible?
# true

expression = expression.reduce
puts expression
# 14

puts expression.reducible?
# false

# 为了节省精力，我们将上述求值的过程封装到一个机器里面：
class Machine < Struct.new(:expression)
    def step
        self.expression = expression.reduce
    end

    def run
        while expression.reducible?
            puts expression
            step
        end
        puts expression
    end
end

Machine.new(
    Add.new(
        Multiply.new(Number.new(1), Number.new(2)),
        Multiply.new(Number.new(3), Number.new(4))
    )
).run

# 1 * 2 + 3 * 4
# 2 + 3 * 4
# 2 + 12
# 14

# 对布尔值和小于运算的实现
class Boolean < Struct.new(:value)
    def to_s
        value.to_s
    end

    def inspect
        "<<#{self}>>"
    end 

    def reducible?
        false
    end
end

class LessThan < Struct.new(:left, :right)
    def to_s
        "#{left} < #{right}"
    end

    def inspect
        "<<#{self}>>"
    end

    def reducible?
        true
    end

    def reduce
        if left.reducible?
            LessThan.new(left.reduce, right)
        elsif right.reducible?
            LessThan.new(left, right.reduce)
        else
            Boolean.new(left.value < right.value)
        end
    end
end


Machine.new(
    LessThan.new(Number.new(5), Add.new(Number.new(2), Number.new(2)))
    ).run
# 5 < 2 + 2
# 5 < 4 
# false



# 添加变量
class Variable < Struct.new(:name)
    def to_s
        name.to_s
    end

    def inspect
        "<<#{self}>>"
    end

    def reducible?
        true
    end
end


# 环境
# 为了规约一个变量，机器不仅仅需要储存当前的表达式，还需要储存懂
# 变量名称到它的值的映射,这个称作环境。
# 在ruby 中，我们可以把这种映射实现成一个散列表，以统符号作为键，
# 用表达式作为值，如hash{x:Number.new(2), y:Boolean.new(false)}
# 表是一个环境，它分别将变量x,y 和Simple 的数字和布尔值进行了关联

class Variable
    def reduce(environment)
        environment[name]
    end
end

# 我们将一个环境作为参数传进#reduce， 因此需要修改其他类的实现，
# 以便能够接受这个参数
class Add
    def reduce(environment)
        if left.reducible?
            Add.new(left.reduce(environment), right)
        elsif right.reducible?
            Add.new(left, right.reduce(environment))
        else
            Number.new(left.value + right.value)
        end
    end
end

class Multiply
    def reduce(environment)
        if left.reducible?
            Multiply.new(left.reduce(environment), right)
        elsif right.reducible?
            Multiply.new(left, right.reduce(environment))
        else
            Number.new(left.value * right.value)
        end
    end
end 


class LessThan
    def reduce(environment)
        if left.reducible?
            LessThan.new(left.reduce(environment), right)
        elsif right.reducible?
            LessThan.new(left, right.reduce(environment))
        else
            Boolean.new(left.value < right.value)
        end
    end
end

# 现在reduce 的所有实现更新之后都可以支持环境了,因此还需要重新定义虚拟机
# 以便可以维持一个环境并将它提供给 reduce 方法
Object.send(:remove_const, :Machine)    # 忘记原来的Machine 类

class Machine < Struct.new(:expression, :environment)
    def step
        self.expression = expression.reduce(environment)
    end

    def run
        while expression.reducible?
            puts expression
            step
        end

        puts expression
    end
end

# 机器的run 方法没有改变，但是它有了一个新的环境属性，
# 这个属性提供给step 方法续保的实现使用
Machine.new(
    Add.new(Variable.new(:x), Variable.new(:y)),
    {x: Number.new(3), y: Number.new(4)}
).run
# 3 + y
# 3 + 4
# 7

# 语句实现
# 一个语句可以通过求值改变抽象机器的状态，机器唯一的状态
# （除了当前程序）就是环境，因此我们允许Simple 的语句生成一个新的环境
# 以替代当前的环境

# 最简单的语句是什么也不做：既不能规约，也无法对环境产生任何影响
class DoNothing # 1
    def to_s
        'do-nothing'
    end

    def inspect
        "<<#{self}>>"
    end

    def ==(other_statement)    # 2
        other_statement.instance_of?(DoNothing)
    end

    def reducible?
        false
    end
end
# 1
# 所有的语法类都是从Struct 类继承，但是DoNothing 没有继承任何类
# 因为DoNothing 什么属性都没有，并且Struct.new 不允许我们传一个空的名称列表

# 2
# 想要比较任何两个语句是否相等。
# 其他类从Struct 那里继承了 == 的实现，但是DoNothing 只能自行定义

# 一个什么都不做的语句看起来什么意义都没有,其实可以用来表示程序已经执行成功
# 其他语句在执行完毕之后,我们会将它们最终规约成 <<do-nothing>>


# ----------------------------------------------------------
# << x = x + 1>> 赋值语句的实现
# 一个赋值语句,是由: 变量名, 等号, 表达式 共同组成
# 如果赋值语句是可规约的，我们就按照表达式规约规则对其进行规约，并
# 最终得到一个报含规约后表达式的新的赋值语句
# 如当变量x = 2, 进入环境 x = x + 1,进行规约,会得到<<x = 2 + 1>>
# 然后规约就得到了<<x = 3>>

# 若是表达式已经为<<3>>,那么就需要进行赋值,意味着对环境进行更新,即将值
# 与适当的变量名关联起来.

# 因此，规约一个语句，不单需要生成一个规约了的新语句，还需要一个新的环境，
# 这个换南京有时候会和执行规约的环境不同
# ----------------------------------------------------------

# 我们使用hash 的merge 方法来创建新的散列来更新环境，不会改变旧值
old_environment = {y: Number.new(5)}
new_environment = old_environment.merge({x: Number.new(3)})
puts new_environment
# {:y=><<5>>, :x=><<3>>}
puts old_environment
# {:y=><<5>>}

# 这种环境改变并不具有破坏性，因为我们选择了新建一个环境，而不是在原本的
# 环境上进行改变，实际上，我们也应该尽量避免破坏性的修改。
# 如果reduce 想要改变当前的环境，那么它就必须传给调用者一个新的环境，
# 否则,就不会产生任何变化, 于是就避免了修改

# 以上两点强化了表达式和语句的区别:
# 表达式: 不会得到新的环境, 因此不会改变环境
# 语句：会得到新的环境，表明规约一个语句，会对环境产生影响

# 总结：赋值的规约规则如下：
# 1. 如果赋值表达式能规约，那么就对其规约，
# 得到的结果讲就是一个规约了的赋值语句和一个没有改变的环境
# 2. 如果赋值表达式不能规约,那么就更新环境把这个表达式与赋值的变量关联起来
# 得到的结果是一个<<do-nothing>> 语句和一个新的环境
# 这样，我们就能实现赋值类Assign 的足够信息，唯一的困难，是Assign 的
# reduce 需要既返回一个语句，又返回一个环境，而ruby 只能返回一个对象，但我
# 们可以把它们都放到数组中，就模拟了这种情况


class Assign < Struct.new(:name, :expression)
    def to_s
        "#{name} = #{expression}"
    end

    def inspect
        "<<#{self}>>"
    end

    def reducible?
        true
    end

    def reduce(environment)
        if expression.reducible?
            [Assign.new(name, expression.reduce(environment)), environment]
            # 总结1
        else
            [DoNothing.new, environment.merge({name => expression})]
            # 总结2
        end
    end
end

# 上面的Assign 规则保证了，如果一个表达式不可规约，那就只会增加到变量上
statement = Assign.new(:x, Add.new(Variable.new(:x), Number.new(1)))
puts statement
# x = x + 1

environment = { x: Number.new(2)}
puts environment
# {:x=><<2>>}
puts statement.reducible?
# true
statement, environment = statement.reduce(environment)
puts statement, environment
# irb: [<<x = 2 + 1>>, {:x=><<2>>}]
statement, environment = statement.reduce(environment)
puts statement, environment
# irb: [<<x = 3>>, {:x=><2>>}]
statement, environment = statement.reduce(environment)
puts statement, environment
# [<<do-nothing>>, {:x=><<3>>}]

puts statement.reducible?
# false

# 为了处理语句，需要重新实现虚拟机，让它能够在每一步规约时候显示当前语句和环境

Object.send(:remove_const, :Machine)   # 清空当前虚拟机
class Machine < Struct.new(:statement, :environment)
    def step
        self.statement, self.environment = statement.reduce(environment)
    end

    def run
        while statement.reducible?
            puts "#{statement}, #{environment}"
            step
        end

        puts "#{statement}, #{environment}"
    end
end

Machine.new(
    Assign.new(:x, Add.new(Variable.new(:x), Number.new(1))), 
    {x: Number.new(2)}
).run
# x = x + 1, {:x=><<2>>}
# x = 2 + 1, {:x=><<2>>}
# x = 3, {:x=><<2>>}
# do-nothing, {:x=><<3>>}



# if 条件语句
# if(x){y=1} else {y=2}
# 第一个<<y=1>>， 称作结果
# 第二个<<y=2>>，称作替换语句

# if 条件语句规约规则：
# 1. 如果条件能规约，那就对其进行规约，得到的结果就是一个规约了德条件语句和
# 一个没有改变的环境
# 2. 如果条件是表达式<<true>> 了，就规约成结果语句和一个没有变化的环境
# 3. 如果条件是表达式<<false>> 了，就规约成替换语句和一个没有变化的环境
class If < Struct.new(:condition, :consequence, :alternative)
    def to_s
        "if(#{condition}) { #{ consequence } } else { #{alternative} } "
    end

    def inspect
        "<<#{self}>>"
    end

    def reducible?
        true
    end

    def reduce(environment) 
        if condition.reducible?
            [If.new(condition.reduce(environment), consequence, alternative), environment]
        else
            case condition
            when Boolean.new(true)
                [consequence, environment]
            when Boolean.new(false)
                [alternative, environment]
            end
        end
    end
end

# 规约操作
Machine.new(
    If.new(
        Variable.new(:x),
        Assign.new(:y, Number.new(1)),
        Assign.new(:y, Number.new(2))
    ),
    {x: Boolean.new(true)}
).run
# if(x) { y = 1 } else { y = 2 } , {:x=><<true>>}
# if(true) { y = 1 } else { y = 2 } , {:x=><<true>>}
# y = 1, {:x=><<true>>}
# do-nothing, {:x=><<true>>, :y=><<1>>}

# 支持不带else 从句的条件语句如下：
Machine.new(
    If.new(Variable.new(:x), Assign.new(:y, Number.new(1)), DoNothing.new),
    {x: Boolean.new(false)}
).run

# if(x) { y = 1 } else { do-nothing } , {:x=><<false>>}
# if(false) { y = 1 } else { do-nothing } , {:x=><<false>>}
# do-nothing, {:x=><<false>>}

# 但是我们目前不能把这些基础“材料”联系到一起，没有办法
# 刚给多个变量赋值挥着进行多个条件运算，因此，我们需要再定义一种语句：序列(sequence)

# 对序列进行规约的规则如下：
# 1.如果第一条是<<do-nothing>>，就规约成第二条语句和原始的环境
# 2.如果第一条不是<<do-nothing>>，就对其进行规约，得到的结果就是一个新的序列
# （规约之后的第一条语句，后面跟着第二条语句）和一个规约了的环境

class Sequence < Struct.new(:first, :second)
    def to_s
        "#{first};#{second}"
    end

    def inspect
        "<<#{self}>>"
    end

    def reducible?
        true
    end

    def reduce(environment)
        case first
        when DoNothing.new
            [second, environment]
        else
            reduced_first, reduced_environment = first.reduce(environment)
            [Sequence.new(reduced_first, second), reduced_environment]
        end
    end
end

# 规则的总体效果是：不断去规约一个序列时，一直都在规约它的第一个语句，直到
# 成为<<do-nothing>>，然后再去规约第二个语句。效果如下：

Machine.new(
    Sequence.new(
    Assign.new(:x, Add.new(Number.new(1), Number.new(1))),
    Assign.new(:y, Add.new(Variable.new(:x), Number.new(3)))
    ),
    {}
).run
# x = 1 + 1;y = x + 3, {}
# x = 2;y = x + 3, {}
# do-nothing;y = x + 3, {:x=><<2>>}
# y = x + 3, {:x=><<2>>}
# y = 2 + 3, {:x=><<2>>}
# y = 5, {:x=><<2>>}
# do-nothing, {:x=><<2>>, :y=><<5>>}



# 新增无限循环while 
# 对while 的规约规则：
# 把   <<while (条件) { 语句主体 }>> 
# 规约成<<if (条件) { 语句主体; while (条件) { 语句主体 }} else { do-nothing }
# 具体实现如下：
class While < Struct.new(:condition, :body)
    def to_s
        "while (#{condition}) { #{body} }"
    end

    def inspect
        "<<#{self}>>"
    end

    def reducible?
        true
    end

    def reduce(environment)
        [If.new(condition, Sequence.new(body, self), DoNothing.new), environment]
    end
end

# 这样虚拟机就可以根据需要对条件和语句主体进行求值
Machine.new(
    While.new(
        LessThan.new(Variable.new(:x), Number.new(5)),
        Assign.new(:x, Multiply.new(Variable.new(:x), Number.new(3)))
    ),
    { x:Number.new(1) }
).run
# while (x < 5) { x = x * 3 }, {:x=><<1>>}
# if(x < 5) { x = x * 3;while (x < 5) { x = x * 3 } } else { do-nothing } , {:x=><<1>>}
# if(1 < 5) { x = x * 3;while (x < 5) { x = x * 3 } } else { do-nothing } , {:x=><<1>>}
# if(true) { x = x * 3;while (x < 5) { x = x * 3 } } else { do-nothing } , {:x=><<1>>}
# x = x * 3;while (x < 5) { x = x * 3 }, {:x=><<1>>}
# x = 1 * 3;while (x < 5) { x = x * 3 }, {:x=><<1>>}
# x = 3;while (x < 5) { x = x * 3 }, {:x=><<1>>}
# do-nothing;while (x < 5) { x = x * 3 }, {:x=><<3>>}
# while (x < 5) { x = x * 3 }, {:x=><<3>>}
# if(x < 5) { x = x * 3;while (x < 5) { x = x * 3 } } else { do-nothing } , {:x=><<3>>}
# if(3 < 5) { x = x * 3;while (x < 5) { x = x * 3 } } else { do-nothing } , {:x=><<3>>}
# if(true) { x = x * 3;while (x < 5) { x = x * 3 } } else { do-nothing } , {:x=><<3>>}
# x = x * 3;while (x < 5) { x = x * 3 }, {:x=><<3>>}
# x = 3 * 3;while (x < 5) { x = x * 3 }, {:x=><<3>>}
# x = 9;while (x < 5) { x = x * 3 }, {:x=><<3>>}
# do-nothing;while (x < 5) { x = x * 3 }, {:x=><<9>>}
# while (x < 5) { x = x * 3 }, {:x=><<9>>}
# if(x < 5) { x = x * 3;while (x < 5) { x = x * 3 } } else { do-nothing } , {:x=><<9>>}
# if(9 < 5) { x = x * 3;while (x < 5) { x = x * 3 } } else { do-nothing } , {:x=><<9>>}
# if(false) { x = x * 3;while (x < 5) { x = x * 3 } } else { do-nothing } , {:x=><<9>>}
# do-nothing, {:x=><<9>>}


# 正确性：如果程序只是语法上有效，而实际上是错误的，
# 如<<x = true; x = x + 1>>，实际上这时候机器会停止，代码如下：

# Machine.new(
#     Sequence.new(
#         Assign.new(:x, Boolean.new(true)),
#         Assign.new(:x, Add.new(Variable.new(:x), Number.new(1)))
#         ),
#         {}
# ).run

# 结果：
# x = true;x = x + 1, {}
# do-nothing;x = x + 1, {:x=><<true>>}
# x = x + 1, {:x=><<true>>}
# x = true + 1, {:x=><<true>>}
# Uncaught exception: undefined method `+' for true:TrueClass

# Simple 表达式会返回一个值，而语句不会
# Simple 的环境只与已经完全规约成值的变量有关，而不与待执行的更大的表达式关联
# 我们可以通过改变小步语义来改变上面任何的运行策略，这将描述一种新语言，这种语言拥有同样的语法
# 但是有着不同的运行时行为

# 小步语义的细节化、面向执行的风格能够让他无歧义的定义真实世界的编程语言